Flatten binary tree to linked list

Time: O(N); Space: O(H); medium

Given a binary tree, flatten it to a linked list in-place.

Example 1:

Input: root = {TreeNode}

    1
   / \
  2   5
 / \   \
3   4   6

Output: The flattened tree should look like:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

[1]:

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

[3]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(H), H is height of binary tree
    """
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: nothing, do it in place
        """
        self.flattenRecu(root, None)

    def flattenRecu(self, root, list_head):
        if root:
            list_head = self.flattenRecu(root.right, list_head)
            list_head = self.flattenRecu(root.left, list_head)
            root.right = list_head
            root.left = None
            return root
        else:
            return list_head

[11]:

s = Solution1()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.right = TreeNode(6)
s.flatten(root)
assert root.val == 1
assert root.right.val == 2
assert root.right.right.val == 3
assert root.right.right.right.val == 4
assert root.right.right.right.right.val == 5
assert root.right.right.right.right.right.val == 6

[12]:

class Solution2(object):
    list_head = None

    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: nothing, do it in place
        """
        if root:
            self.flatten(root.right)
            self.flatten(root.left)
            root.right = self.list_head
            root.left = None
            self.list_head = root

[13]:

s = Solution2()
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.right = TreeNode(6)
s.flatten(root)
assert root.val == 1
assert root.right.val == 2
assert root.right.right.val == 3
assert root.right.right.right.val == 4
assert root.right.right.right.right.val == 5
assert root.right.right.right.right.right.val == 6